package com.lmk.dsa.struct.heap;

import com.lmk.dsa.struct.commons.KvNode;

/**
 * 抽象的堆实现
 * @author LaoMake
 * @since 1.0
 */
public abstract class AbstractHeap implements Heap {

    /** 数据数组 */
    protected KvNode[] nodes;

    /** 堆容量：静态数组的长度 */
    protected Integer capacity;

    /** 堆中数据节点的总数 */
    protected Integer size;

    /**
     * 对指定索引位置的元素进行上浮操作
     * @param childIndex
     */
    protected abstract void siftUp(int childIndex);

    /**
     * 对指定索引位置的元素进行下沉操作
     * @param parentIndex
     */
    protected abstract void siftDown(int parentIndex);

    public AbstractHeap() {
        this.capacity = 20;
        this.size = 0;
        this.nodes = new KvNode[capacity];
    }

    public AbstractHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.nodes = new KvNode[capacity];
    }

    /**
     * 将任意数组转换成堆
     * @param array
     */
    public AbstractHeap(KvNode[] array) {
        // 数组原地堆化
        this.capacity = this.size = array.length;
        this.nodes = array;
        heapify();
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    @Override
    public void add(KvNode node) {
        // 数组已满，进行扩容操作
        if(size == nodes.length){
            grow();
        }

        nodes[size] = node;
        siftUp(size);
        size++;
    }

    @Override
    public <K extends Comparable<? super K>, V> void add(K key, V value) {
        add(new KvNode(key, value));
    }

    @Override
    public <K extends Comparable<? super K>, V> boolean contain(K key) {
        boolean contains = false;
        for (KvNode node : nodes){
            if(node.key.compareTo(key) == 0){
                contains = true;
                break;
            }
        }
        return contains;
    }

    @Override
    public <K extends Comparable<? super K>, V> void change(K key, V value) {
        for (KvNode node : nodes){
            if(node.key.compareTo(key) == 0){
                node.value = value;
                break;
            }
        }
    }

    @Override
    public KvNode pool() {
        KvNode node = nodes[0];
        nodes[0] = nodes[--size];
        siftDown(0);
        return node;
    }

    /**
     * 根据孩子节点的索引获取父节点索引
     * @param child
     * @return
     */
    protected int parent(int child){
        return (child - 1) / 2;
    }

    /**
     * 根据父节点的索引获取左孩子的索引
     * @param parent
     * @return
     */
    protected int leftChild(int parent){
        return parent * 2 + 1;
    }

    /**
     * 根据父节点的索引获取右孩子的索引
     * @param parent
     * @return
     */
    protected int rightChild(int parent){
        return parent * 2 + 2;
    }

    /**
     * 交换两个位置的元素
     * @param i
     * @param j
     */
    protected void swap(int i, int j){
        KvNode node = nodes[i];
        nodes[i] = nodes[j];
        nodes[j] = node;
    }

    /**
     * 数组扩容，默认增长为原来的1.5倍
     */
    protected void grow(){
        int len = nodes.length;
        len += len >> 1;
        capacity = len;
        KvNode[] data = new KvNode[capacity];
        System.arraycopy(nodes, 0, data, 0, size);
        nodes = data;
    }

    /**
     * 转换为数组
     * @return
     */
    public Object[] toArray(){
        KvNode[] result = new KvNode[size];
        System.arraycopy(nodes, 0, result, 0, size);
        return result;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(nodes[i]).append(", ");
        }

        if (size > 0){
            sb.delete(sb.length() - 2, sb.length());
        }
        sb.append("]");
        return sb.toString();
    }

    @Override
    public KvNode[] sort() {
        while (size > 0){
            swap(0, --size);
            siftDown(0);
        }
        return this.nodes;
    }

    /**
     * 原地堆化
     */
    protected void heapify(){
        // Heapify，从最后一个非叶子节点开始，依次对之前的每个节点进行下沉操作
        int index = parent(size - 1);
        while(index >= 0){
            siftDown(index--);
        }
    }
}
